/**
      <one line to give the program's name and a brief idea of what it does.>
    Copyright (C) <2011>  <André Mendes de Oliveira Paiva>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  
 */

package estrutura.lista;

import estrutura.EstruturaDados;
import estrutura.No;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.List;
import java.util.ArrayList;

public class ListaDinamica extends EstruturaDados {

    private List<NoLista> vertices;

    public ListaDinamica(String nome, int qtdeNo) {
        super(nome, qtdeNo);
        vertices = new ArrayList<NoLista>(qtdeNo);
    }
    public ListaDinamica(String nome) {
        this(nome, QTDE_MAX_NO);
    }

    public ListaDinamica(int qtdeNo) {
        this(NOME_ESTRUTURA_ANONIMA, qtdeNo);
    }

    public ListaDinamica() {
        this(NOME_ESTRUTURA_ANONIMA, QTDE_MAX_NO);
    }
    private int obterMaxId()
    {
        int maxId = 0;
        for (NoLista no : vertices)
        {
            if (no == null) break;
            if (no.getId() > maxId) {
                maxId = no.getId();
            }
        }
        return maxId;
    }
    public boolean inserirNo(String valor) {
        boolean ret = false;
        if (vertices.size() < this.getQtdeNo()) {
            /* Cria o nó e adiciona-o ao vetor de vertices */
            NoLista novoNo = new NoLista(this.obterMaxId()+1, valor);
            ret = vertices.add(novoNo);
        }
        return ret;
    }

    /* Otem um determinado no a partir do ID do Nó */
    public NoLista obterNo(int idNo) {
        NoLista noPesq = null;
        /* Pesquisa o ID do Nó */
        for (NoLista no : vertices) {
            if (no.getId() == idNo) {
                noPesq = no;
                break;
            }
        }
        /* Verifica se a posição do vetor contem um nó válido */
        if (noPesq == null) {
            System.out.println("O ID [" + idNo + "] nao existe.");
        }
        return noPesq;
    }

    /* Obtem o indice de um determinado no a partir do ID do Nó */
    public int obterIndiceNo(int idNo) {
        int id = -1;
        /* Pesquisa o ID do Nó */
        for (int i = 0; i < vertices.size(); i++) {
            if (vertices.get(i) != null && vertices.get(i).getId() == idNo) {
                id = i;
                break;
            }
        }
        return id;
    }

    /* Obtem o ID de um determinado no a partir do valor Nó */
    public int obterIdPorValor(String valor)
    {
       int i = -1;
        /* Pesquisa o Valor do Nó */
        for (NoLista no : vertices) {
            if (no.getValor().equals(valor)) {
                i = no.getId();
                break;
            }
        }
        return i;
    }

    /* Obtem o Id do nó Origem,, ou seja o nó que não é destino de nenhum outro nó */
    public int obterIDNoOrigem()
    {
       int i, j, id = -1;
       for (i = 0; i < this.vertices.size(); i++)
       {
         for (j = 0; j < this.vertices.size(); j++)
         {
           /* Verifica se o Nó na posição i faz parte de alguma aresta como nó destino */
           if (vertices.get(j) != null && vertices.get(j).obterAresta(vertices.get(i).getId()) != null)
              break;
         }
         /* Não achou nenhuma aresta com nó destino de i, então ele é o nó origem */
         if (j == this.vertices.size())
         {
            id = vertices.get(i).getId();
            break;
         }
       }
       return id;
    }
    
    public ArestaLista obterAresta(int idNoOrigem, int idNoDestino) {
        ArestaLista aresta = null;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            aresta = noOrigem.obterAresta(idNoDestino);
        }
        noOrigem = null;
        return aresta;
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino) {
        return inserirAresta(idNoOrigem, idNoDestino, null, 0);
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo) {
        return inserirAresta(idNoOrigem, idNoDestino, rotulo, 0);
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo, int peso) {
        /* verifia se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        NoLista noDestino = this.obterNo(idNoDestino);
        if (noOrigem != null && noDestino != null) {
            ret = noOrigem.addAresta(noDestino, rotulo, peso);
        }
        noOrigem = null;
        noDestino = null;
        return ret;
    }

    public boolean inserirRotulo(int idNoOrigem, int idNoDestino, Object rotulo) {
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.addRotulo(idNoDestino, rotulo);
        }
        return ret;
    }

    public boolean excluirNo(int idNo) {
        boolean ret = false;
        NoLista no = this.obterNo(idNo);
        if (no != null) {
            /* remove todas as arestas */
            no.removeAllAresta();
            /* exclui as Arestas dos outros nós que tenham ligação com este nó  */
            for (NoLista noAux : vertices) {
                /* Se não for o mesmo Nó, então chama rotina para exclui A aresta com este nó */
                if (noAux.getId() != idNo) {
                    noAux.removeAresta(idNo);
                }
            }
            /* exclui o nó */
            vertices.remove(no);
            ret = true;
        }
        return ret;
    }

    public boolean excluirAresta(int idNoOrigem, int idNoDestino) {
        /* verifia se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.removeAresta(idNoDestino);
        }
        noOrigem = null;
        return ret;
    }
    @Override
    public boolean excluirTodasArestas(int idNo) {
        /* verifica se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNo);
        if (noOrigem != null) {
            ret = noOrigem.removeAllAresta();
        }
        return ret;
    }
   @Override
    public boolean excluirRotulo(int idNoOrigem, int idNoDestino) {
        /* verifica se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.removeRotulo(idNoDestino);
        }
        return ret;
    }
    @Override
    public void imprimir() {
        System.out.println(super.toString());
        for (NoLista no : vertices) {
          no.imprimir();
        }
    }

    public void imprimirNosVizinhos(int id) {
        int i = this.obterIndiceNo(id);
        if (i != - 1 && vertices.get(i) != null)
          vertices.get(i).imprimir();
    }
    /* Retorna o idNoice da primeira Aresta encontrada ou -1 senão existir aresta*/
    public int obterIDPrimeiraAresta(int idNo) {
        int id = -1;
        NoLista no = this.obterNo(idNo);
        if (no != null) {
            id = no.getIDPrimeiraAresta();
        }
        return id;
    }

    /* Retorna o id da próxima Aresta encontrada ou -1 senão existir aresta*/
    @Override
    public int obterIDProximaAresta(int idNoOrigem, int idNoDestino) {
        int id = -1;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            id = noOrigem.getIDProximaAresta(idNoDestino);
        }
        return id;
    }

    /* Retorna o rotulo da ligação ou null senão não existir aresta*/
    public Object obterRotuloAresta(int idNoOrigem, int idNoDestino) {
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            return noOrigem.getRotuloAresta(idNoDestino);
        }
        return null;
    }

    public boolean obterDadosArquivo(String arquivo)
    {
        boolean res = true;
        String linha;
        try
        {
          FileReader      fr = new FileReader(arquivo);
          BufferedReader  br = new BufferedReader(fr);
          String []nos;      /* vetor de nós, obtido a partir da 1ª linha do arquivo */
          String []arestas;  /* vetor de arestas, obtido a partir da 2ª linha do arquivo */
          /* Lê a primeira linha, contendo os nós */
          linha = br.readLine();
          if (linha != null)
          {
            nos =  linha.split(";");
            /* insere os nós */
            for(int i = 0; i < nos.length; i++)
            {
                if (!(nos[i].trim()).equals(""))
                  this.inserirNo(nos[i]);
            }
          }
          int indNoOrigem;
          /* Lê as arestas e inclui as mesmas no grafo */
          while ((linha = br.readLine()) != null)
          {
             arestas = linha.split(";");
             /* obtem o ID do nó de origem, a partir do valor do nó */
             indNoOrigem = (this.obterIdPorValor(arestas[0]));
             if (indNoOrigem != -1)
             {
                for(int i = 1; i < arestas.length; i++)
                {
                   /* Se o valor for 1, então é para criar a aresta */
                    if ((arestas[i].trim()).equals("1.0"))
                      this.inserirAresta(indNoOrigem, i);
                }
             }
          }
        }
        catch (Exception e)
        {
           System.out.println("Erro ao obter os dados do arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }
    public boolean gerarArquivoEstrutura(String arquivo)
    {
        boolean res = true;
        String linha="";
        try
        {
          FileWriter      fr = new FileWriter(arquivo);
          BufferedWriter  br = new BufferedWriter(fr);
          /* Lê os nós */
          for(NoLista no : vertices)
          {
            linha += ";" + no.getValor();
          }
          /* grava a primeira linha do arquivo com os nós */
          br.write(linha);
          NoLista no;
          /* Lê né e verifica as conexões do mesmo */
          for (int i = 0; i < vertices.size(); i++ )
          {
            no = vertices.get(i);
            linha = no.getValor();
            for (int j = 0; j < vertices.size(); j++ )
            {
               if ( no.obterAresta(j+1) != null )
                 linha += ";" + "1.0";
               else
                 linha += ";" + "0";
            }
            /* grava linha de arestas do nó */
            br.write("\n");
            br.write(linha);
          }
         br.close();
        }
        catch (Exception e)
        {
           System.out.println("Erro ao gravar os dados no arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }
    /* Obtem o Id do nó Destino, ou seja o nó que não é origem de nenhum outro nó */
    public int obterIDNoDestino()
    {
       int i, id = -1;
       for (i = 0; i < this.vertices.size(); i++)
       {
         /* Não possui nenhuma aresta, então ele é o nó Destino */
         if (this.vertices.get(i).getAresta() == null )
         {
            id = this.vertices.get(i).getId();
            break;
         }
       }
       return id;
    }

    public ArrayList<No> obterVertices() {
        ArrayList <No> listaNo = new ArrayList<No>();
        for(int i = 0; i < vertices.size(); i++)
            if (vertices.get(i) != null)
               listaNo.add(vertices.get(i));
       return listaNo;
    }

    public ArrayList<No> obterNosVizinhos(int idNo)
    {
       NoLista no = this.obterNo(idNo);
       if (no != null)
           return no.obterNosVizinhos();
       else
           return null;
    }

    public No obterNoPorID(int idNo)
    {
       return this.obterNo(idNo);
    }
}
